package algorithms.que13;

/**
 * @功能
 * @创建时间 2020/8/1
 */
public class StackQueue<Item> {
    private Stack<Item> H = new Stack<Item>();
    private Stack<Item> T = new Stack<Item>();
    private Stack<Item> Hbuffer = new Stack<Item>();
    private Stack<Item> Hflip = new Stack<Item>();
    private Stack<Item> Tadd = new Stack<Item>();
    private Stack<Item> sp;

    private int popCnt;
    private int N = 0;
    private int sizeofH = 0;  //被peek后H中剩余的元素个数

    public boolean isEmpty() {
        return H.isEmpty() && T.isEmpty() && Hbuffer.isEmpty()
                && Hflip.isEmpty() && Tadd.isEmpty();
    }

    public int size() {
        return N;
    }

    private void popPush(Stack<Item> s1, Stack<Item> s2) {  //s1弹出一个元素后压入s2
        if(!s1.isEmpty())
            s2.push(s1.pop());
    }

    private void peekPush(Stack<Item> s1, Stack<Item> s2) {  //H peek一个元素后压入Hflip
        if(!s1.isEmpty() && sizeofH > 0) {
            s2.push(s1.peek());
            sizeofH --;
        }
    }

    private void swap() {
        H.clear(); sp = H; H = Hbuffer; Hbuffer = sp;
        T.clear(); sp = T; T = Tadd; Tadd = sp;
        popCnt  = H.size() + T.size();
        sizeofH = H.size();
    }

    public void enQueue(Item item) {
        //入队
        if(Hbuffer.isEmpty()) {
            T.push(item);
            popCnt ++;
        } else
            Tadd.push(item);
        //整理
        //sizeofH < T.size() 说明H未peek完全，T中仍有元素，需要移动
        //sizeofH >= H.size() && T.isEmpty() 说明H中还有元素在被peek前先被pop，需要移动
        if(!T.isEmpty() || (sizeofH >= H.size() && T.isEmpty())) {
            popPush(T, Hbuffer); peekPush(H, Hflip);
            if(T.isEmpty() && Hflip.isEmpty())
                swap();
        } else if(T.isEmpty()) {
            if(!Hflip.isEmpty()) {
                popPush(Hflip, Hbuffer);
                if(Hflip.isEmpty() && T.isEmpty())
                    swap();
            } else if(Hflip.isEmpty() && T.isEmpty() && H.isEmpty())
                swap();
        }
        N ++;
    }

    public  Item deQueue() {
        Item item;
        //先出
        if(!H.isEmpty()) {
            item = H.pop();
            popCnt --;
            popPush(T, Hbuffer);
        }
        else
            item = null;

        //出完后整理
        if(H.isEmpty()) {  //H为空
            if(N > 0 ) {  //还有元素
                swap(); Hflip.clear();
            }
        } else {  //H不为空
            if(T.isEmpty())  {  //T为空
                if(Hbuffer.size() + H.size() > popCnt && popCnt - Hbuffer.size() <=1) {
                    swap(); Hflip.clear();
                } else if(popCnt < H.size() + Hbuffer.size())
                    popPush(Hflip, Hbuffer);
            }
        }

        N --;
        return item;
    }
}
